package Csp.Solvers;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import Csp.Model.Csp;
import Csp.Model.Variable;

public class Backtracking implements ISolver {

	private IHeuristics heuristics;
	private long time;
	private long timeout;
	private int nodes;
	
	public Backtracking(IHeuristics heuristics, int timeout){
		this.heuristics = heuristics;
		this.timeout = timeout;
	}
	
	@Override
	public List<Variable> solve(Csp csp) {
		nodes = 0;
		time = System.currentTimeMillis();
		List<Variable> result = backtrack(new ArrayList<Variable>(), csp);
		time = System.currentTimeMillis() - time;
		return result;
	}
	
	private List<Variable> backtrack(List<Variable> instance, Csp csp){
		
		if(System.currentTimeMillis() - time > timeout*1000){
			System.err.print("TIMEOUT!");
			return new ArrayList<Variable>();
		}
			
		if(instance.size() == csp.getVariables().size())
			return instance;
		
		Variable  variable = heuristics.selectVariable(instance, csp);
		Set<Integer> domain = new HashSet<Integer>(variable.getDomain());
		
		while(!domain.isEmpty()){
			int value = heuristics.selectValue(variable, domain, csp);
			Variable  newVar = new Variable(variable.getId(), value);
			//Per benchmark: #nodi albero di ricerca
			nodes++;
			if(csp.isConsistent(instance, newVar)){
				List<Variable> newInstance = new ArrayList<Variable>(instance);
				newInstance.add(newVar);
				Csp consCsp = cons(newInstance, newVar, csp);
				if(consCsp != null){
					List<Variable> result = backtrack(newInstance, consCsp);
					if(result != null)
						return result;
				}
			}
		}
		
		return null;
	}

	@Override
	public Csp cons(List<Variable> instance, Variable last, Csp csp) {
		return csp;
	}

	@Override
	public int getNodes() {
		return nodes;
	}

	@Override
	public long getTime() {
		return time;
	}

	@Override
	public String getName() {
		return this.getClass().getName() + " with "+heuristics.getClass().getName();
	}

}
